This invention relates to the field of integrated circuits. More particularly this invention relates to methods for assigning coordinates to cells of logic trees of integrated circuits in a manner which maintains desirable cell density characteristics.
Microelectronic integrated circuits consist of a large number of electronic components, including individual logic devices or groups of logic devices that are applied to the surface of a substrate, typically a silicon wafer. The components are typically grouped to provide an application-specific integrated circuit. For each application-specific integrated circuit, placement of the components in optimum positions provides efficient layout of the components on the substrate in order to reduce manufacturing costs, processor delays, size and the like. Because the application-specific integrated circuits typically contain hundreds of thousands, if not millions of components, the task of optimizing the placement of components on a substrate surface is not practical without the aid of computers.
Computer aided designs are effective to provide component location on the substrate surface for minimizing interconnection distances, wire sizes, processing times and the like. The smallest component placed on a substrate surface is defined as a xe2x80x9ccell.xe2x80x9d A cell may be a single logic component of a larger logic tree or may be one or more logic trees. Assuming the number of cells N to be in the hundreds of thousands or millions, the number of different ways that the cells can be arranged on the substrate surface is equal to about N factorial. Selecting the optimum placement of the cells is therefore an extremely time consuming task.
Furthermore, despite the use of computer aided design techniques, algorithms used for selecting cell locations on the substrate surface may lead to cell congestion or overpopulation of cells in an area of the substrate surface. Overpopulation or overcrowding of an area of the substrate surface is undesirable from the standpoint of enabling efficient wiring routes, reducing overlapping circuits and the like. Accordingly, there continues to be a need for methods useful to further improve the cell placement on a substrate surface in order to lower substrate costs and increase processor speeds.
The present invention relates to a method for selectively assigning coordinates to cells of a logic tree incorporated into an application-specific integrated circuit formed on a substrate surface. In a preferred embodiment, the method includes the steps of:
(a) determining coordinates of an old logic tree and performing an optimization of the old logic tree to obtain a new logic tree;
(b) determining coordinates for cells of the new logic tree which are connected to an output pin of the new logic tree
(c) determining coordinates for tree entrances to the new logic tree;
(d) determining coordinates for all cells of the old logic tree from the coordinates of the old logic tree determined in step (a),
(e) determining approximate coordinates for the cells of the new logic tree from the coordinates of the cells of a new logic tree connected to the output pin of the new logic tree determined in step (b) and the coordinates of the tree entrances to the new logic tree determined in step (c);
(f) sorting the approximate coordinates determined in step (e) based on the importance of each cell;
(g) determining optimized coordinates for each cell of the new logic tree based on the approximate coordinates of the new logic tree determined in step (e), the sorted approximate coordinates determined in step (f), and the coordinates of the cells of the old logic tree determined in step (d).